#include "DouList.h"

DouList::DouList():size(0)
{
    head = new Node(0);
}

DouList::DouList(const DouList &list)
{
    size = list.size;
    head = new Node(0);
    Node* tp = head;
    Node* np = list.head->next;
    while(np)
    {
        Node *node = new Node(np->value);
        tp->next = node;
        node->prev = tp;
        tp = tp->next;
        np = np->next;
    }
}

DouList &DouList::operator=(const DouList &list)
{
    while(head != nullptr)
    {
        Node *nextNode = head->next;//下一个节点
        if(Free && nextNode)
            Free(nextNode->value);
        delete head;
        head = nextNode;
    }
    tail = nullptr;
    size = list.size;
    head = tail = new Node(0);
    Copy = list.Copy;
    Free = list.Free;
    Print =list.Print;
    Node *tp = head;
    Node *travelPoint = list.head->next;
    while(travelPoint != nullptr)
    {
        Node *newNode = new Node(travelPoint->value);
        if(Free != nullptr)
            newNode->value = Copy(newNode->value);
        tp->next = newNode;
        tp->next->prev = tp;
        tp = tp->next;
        travelPoint = travelPoint->next;
    }
    tail = tp;
    return *this;
}

DouList::~DouList()
{
    while(head != nullptr)
    {
        Node *nextNode = head->next;//下一个节点
        if(Free && nextNode)
            Free(nextNode->value);
        delete head;
        head = nextNode;
    }
    tail = nullptr;
}

void DouList::InsertTail(const ElementType &element)
{
    Node *node = new Node(element);
    Node* tp = head->next;
    while(tp)
        tp =tp->next;
    tp->next = node;
    node->prev = tp;
    tail = node;
    size++;
}

void DouList::InsertByIndex(size_t index, const ElementType &element)
{
    if(index >= size)
    {
        return;
    }
    Node *tp = head;
    for(int i = 0;i < index;i++)
    {
        tp = tp->next;
    }
    Node* node = new Node(element);
    node->next = tp->next;
    tp->next = node;
    node->prev = tp;
    size++;

}

void DouList::RemoveByIndex(size_t index)
{
    if(index >= size)
        return;
    Node *tp = head;
    for(int i = 0;i < index;i++)
        tp = tp->next;
    Node *node = tp->next;
    tp->next = node->next;
    node->next->prev = tp;
    if(node->next == nullptr)
        tail = tp;
    delete node;
    size--;
}

void DouList::RemoveByElemnt(const ElementType &element)
{
    Node *tp = head;
    while(tp->next)
    {
        if(tp->next->value == element)
        {
            Node *node = tp->next;
            tp->next = node->next;
            node->next->prev = tp;
            if(node->next == nullptr)
                tail = tp;
            delete node;
            size--;
        }
    }
}

DouList::ElementType *DouList::FindByIndex(size_t index)
{
    if(index >= size)
        return nullptr;
    Node *tp = head->next;
    for(int i = 0;i < index;i++)
        tp = tp->next;
    return &tp->value;
}

void DouList::UpdateByIndex(size_t index, const ElementType &element)
{
    if(index >= size)
        return;
    Node *tp = head->next;
    for(int i = 0;i < index;i++)
        tp =tp->next;
    tp->value = element;
}

void DouList::UpdateByElement(const ElementType &oldvalue, const ElementType &newvalue)
{
    Node *tp = head->next;
    while(tp)
    {
        if(tp->value == oldvalue)
            tp->value = newvalue;
        tp =tp->next;
    }
}

void DouList::Sort()
{
    FastSort(head->next,tail);
}

DouList DouList::Merge(const DouList &list)
{
    return DouList();
}

void DouList::FastSort(Node *start, Node *end)
{
    Node* slow = start;
    Node* fast = start->next;
    Node* temp = start;
    while(fast != end)
    {
        if(fast->value < temp->value)
        {
            slow = slow->next;
            std::swap(slow->value,fast->value);
        }
        fast = fast->next;
    }
    std::swap(slow->value,temp->value);
    FastSort(start,slow);
    FastSort(slow->next,end);
}
